package org.example.leetcode;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/11 16:05
 */

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 1 <= n <= 2 * 10⁴
// 0 <= height[i] <= 10⁵
//
//
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 5150 👎 0

public class Solution42 {

    public static void main(String[] args) {
        Solution42 solution42 = new Solution42();
        int[] height = new int[]{5,5,4,7,8,2,6,9,4,5};
        System.out.println(solution42.trap(height));
    }

    public int trap(int[] height) {

        int sum = 0;
        if(height.length == 1){
            return sum;
        }
        for(int i=0;i<height.length-1;i++){

           int j = getNextSize(i, height[i], height);
           sum += calGap(i,j, height);
           if(j > i){
               i = j - 1;
           }
        }

        return sum;

    }

    private int calGap(int i, int j, int[] height) {
        int cal = 0;
        if(j > i){
            cal = (j-i-1) * Math.min(height[i], height[j]);
            for(int x=i+1;x<j;x++){
                if(height[x] < Math.min(height[i], height[j])){
                    cal -= height[x];
                }
            }
            return cal;
        }
        return cal;
    }

    private int getNextSize(int i, int cur, int[] height) {

        int max = 0;
        int maxIndex = 0;
        if(height[i+1] < cur ){
            for(int x=i+2;x< height.length;x++){
                if(height[x] > max){
                    max = height[x];
                    maxIndex = x;
                }
                if(height[x] >= cur){
                    return x;
                }
            }
        }
        if(max > height[i+1]){
            return maxIndex;
        }
        return 0;
    }

}
